package sort;

import sort.test3_27.QuickSort1;

import java.util.Random;

public class QuickSort {

    public   int[]  quickSort(int [] nums){
        if (nums.length==0){
            return null;
        }
        shuffle(nums);
        sort(nums,0, nums.length-1);
        return nums;
    }

    // 洗牌算法，将输入的数组随机打乱
    private void shuffle(int[] nums) {
        Random rand = new Random();
        int n = nums.length;
        for (int i = 0 ; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    public  void sort(int[] nums,int lo,int hi){
        if (lo>hi){
            return;
        }
        int j=partition(nums,lo,hi);
        sort(nums,0,j-1);
        sort(nums,j+1,hi);
        //Todo:下面是归并排序的时候的做法　　仔细与上面对比　　
//        int mid=(lo+hi)/2;
//        sort(nums,lo,mid);
//        sort(nums,mid+1,hi);
    }

    public  int partition(int[] nums,int lo,int hi){
        int mid=nums[lo];
        int j=lo+1;
        int k=hi;
//        while (j<k){   todo:边界
            while (j<=k){
//            while (j<hi&&nums[j]<mid){   todo:边界
                while (j<hi&&nums[j]<=mid){
                    j++;
            }
            while (k>lo&&nums[k]>mid){
                k--;
            }
            if (j>=k){
                break;
            }
            swap(nums,j,k);
        }
        swap(nums,lo,k);
        return k;
    }

    public  void  swap(int[] nums,int j,int k){
        int temp=nums[j];
        nums[j]=nums[k];
        nums[k]=temp;
    }

    public static void main(String[] args) {
        QuickSort1 quickSort = new QuickSort1();
        int[] nums={7,3,5,4,8};
        quickSort.sort(nums,0, nums.length-1);
        for (int a: nums
             ) {
            System.out.println(a);
        }
    }




}
